package practise.alogrithm.hundredInterviewQuestions;

import practise.alogrithm.hundredInterviewQuestions.Utils.TreeBuilder;
import practise.alogrithm.hundredInterviewQuestions.Utils.TreeNode;

/**
 * convert a tree to a bidirection tree
 */
public class ConvertTreeToBidirectionLink {
    static TreeNode head;

    public static TreeNode convertTree(TreeNode treeNode){
        if(treeNode==null){
            return null;
        }
        TreeNode tail = convertNode(treeNode,null);
//        tail.setRight(head);
//        head.setLeft(tail);
        return head;

    }


    public static TreeNode convertNode(TreeNode current,TreeNode tail){//the return value should be the last handled node
        if(current.getRight()==null && current.getLeft()==null){
            if(head==null){//there the first left leaf, it is the head
                head=current;
            }
            if(tail!=null){
                tail.setRight(current);
                current.setLeft(tail);
            }

            return current;
        }

        if(null!=current.getLeft()){
            tail = convertNode(current.getLeft(),tail);

        }
        current.setLeft(tail);
        tail.setRight(current);
        tail = current;//at this time, current is the last on, and the tail means previous


        if(null!=tail.getRight()){
            tail = convertNode(tail.getRight(),tail);
        }

        return tail;

    }

    public static void  main(String[] args){

        TreeNode treeNode = TreeBuilder.buildTree();
        TreeNode result = convertTree(treeNode);
        while(result.getRight()!=null){
            System.out.print(result.getValue()+"==>");
            if(result.getRight()!=null)
                result=result.getRight();
        }

        System.out.println();
        while(result.getLeft()!=null){
            System.out.print(result.getValue()+"<==");
            result=result.getLeft();
        }

    }


}
